#include <iostream>
#include <stack>
#include <queue>
using namespace std;

template <typename T>
struct TreeNode {
    T value;
    TreeNode *left;
    TreeNode *right;
};

void preorder(TreeNode<int> *root)
{
    if (!root) {
        return;
    }
    cout << root->value << endl;
    preorder(root->left);
    preorder(root->right);
}

void preorder2(TreeNode<int> *root)
{
    if (!root) {
        return;
    }
    stack<TreeNode<int> *> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode<int> *t = s.top();
        cout << t->value << endl;
        s.pop();
        if (t->right) {
            s.push(t->right);
        }
        if (t->left) {
            s.push(t->left);
        }
    }
}

void inorder(TreeNode<int> *root)
{
    if (!root) {
        return;
    }
    inorder(root->left);
    cout << root->value << endl;
    inorder(root->right);
}

void inorder2(TreeNode<int> *root)
{
    if (!root) {
        return;
    }
    stack<TreeNode<int> *> s;
    TreeNode<int> *t = root;
    while (t || !s.empty()) {
        if (t) { /* push all left */
            s.push(t);
            t = t->left;
        } else {
            t = s.top();
            s.pop();
            cout << t->value << endl;
            t = t->right;
        }
    }
}

void postorder(TreeNode<int> *root)
{
    if (!root) {
        return;
    }
    postorder(root->left);
    postorder(root->right);
    cout << root->value << endl;
}

void postorder2(TreeNode<int> *root)
{
    if (!root) {
        return;
    }
    stack<TreeNode<int> *> s;
#if 1
    s.push(root);
    TreeNode<int> *prev = NULL;
    while (!s.empty()) {
        TreeNode<int> *curr = s.top();
        /* traversing down the tree */
        if (!prev || prev->left == curr || prev->right == curr) {
            if (curr->left) {
                s.push(curr->left);
            } else if (curr->right) {
                s.push(curr->right);
            } else {
                cout << curr->value << endl;
                s.pop();
            }
        } else if (curr->left == prev) { /* traversing up the tree from the left */
            if (curr->right) {
                s.push(curr->right);
            } else {
                cout << curr->value << endl;
                s.pop();
            }
        } else if (curr->right == prev) { /* traversing up the tree from the right */
            cout << curr->value << endl;
            s.pop();
        }
        prev = curr;
    }
#else
    stack<TreeNode<int> *> output;
    s.push(root);
    while (!s.empty()) {
        TreeNode<int> *curr = s.top();
        output.push(curr);
        s.pop();
        if (curr->left) {
            s.push(curr->left);
        }
        if (curr->right) {
            s.push(curr->right);
        }
    }
    while (!output.empty()) {
        cout << output.top()->value << endl;
        output.pop();
    }
#endif
}

/* all above including preorder, inorder and postorder are dfsorder */
void bfsorder(TreeNode<int> *root)
{
    if (!root) {
        return;
    }
    queue<TreeNode<int> *> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode<int> *t = q.front();
        cout << t->value << endl;
        q.pop();
        if (t->left) {
            q.push(t->left);
        }
        if (t->right) {
            q.push(t->right);
        }
    }
}

int main()
{
    TreeNode<int> t1, t2, t3, t4, t5, t6, t7, t8, t9, t10, t11;
    t1.value = 1;
    t2.value = 2;
    t3.value = 3;
    t4.value = 4;
    t5.value = 5;
    t6.value = 6;
    t7.value = 7;
    t8.value = 8;
    t9.value = 9;
    t10.value = 10;
    t11.value = 11;
    t1.left = &t2;
    t1.right = &t3;
    t2.left = &t4;
    t2.right = &t5;
    t3.left = &t6;
    t3.right = &t7;
    t4.left = &t8; t4.right = 0;
    t5.left = 0; t5.right = &t9;
    t6.left = 0; t6.right = &t10;
    t7.left = &t11; t7.right = 0;
    t8.left = t8.right = 0;
    t9.left = t9.right = 0;
    t10.left = t10.right = 0;
    t11.left = t11.right = 0;
    //preorder2(&t1); /* 1, 2, 4, 8, 5, 9, 3, 6, 10, 7, 11 */
    //inorder2(&t1); /* 8, 4, 2, 5, 9, 1, 6, 10, 3, 11, 7 */
    //postorder2(&t1); /* 8, 4, 9, 5, 2, 10, 6, 11, 7, 3, 1 */
    bfsorder(&t1);
    return 0;
}
